package com.zyk.grate_offer.class07;

import com.zyk.leetcode.TreeNode;

/**
 * 最少摄像头数量
 * https://leetcode-cn.com/problems/binary-tree-cameras/
 *
 * @author zhangsan
 * @date 2021/5/15 13:08
 */
public class Code02_MinCameraCover {

    public static class Info {
        public long uncovered;  // x没被覆盖, 下方都被覆盖. 最少相机数
        public long coveredNoCamera;    // x被覆盖了, x没安装相机
        public long coveredHasCamera;    // x被覆盖了, x安装了相机

        public Info(long uncovered, long coveredNoCamera, long coveredHasCamera) {
            this.uncovered = uncovered;
            this.coveredNoCamera = coveredNoCamera;
            this.coveredHasCamera = coveredHasCamera;
        }
    }


    public static int minCameraCover(TreeNode root) {
        Info ans = process(root);
        return (int) Math.min(ans.uncovered + 1, Math.min(ans.coveredNoCamera, ans.coveredHasCamera));
    }

    private static Info process(TreeNode X) {
        if (X == null) { // base case
            return new Info(Integer.MAX_VALUE, 0, Integer.MAX_VALUE);
        }

        Info left = process(X.left);
        Info right = process(X.right);
        // x uncovered x自己不被覆盖，x下方所有节点，都被覆盖
        // 左孩子： 左孩子没被覆盖，左孩子以下的点都被覆盖
        // 左孩子被覆盖但没相机，左孩子以下的点都被覆盖
        // 左孩子被覆盖也有相机，左孩子以下的点都被覆盖
        long uncovered = left.coveredNoCamera + right.coveredNoCamera;

        // x下方的点都被covered，x也被cover，但x上没相机
        long coveredNoCamera = Math.min(
                // 1)
                left.coveredHasCamera + right.coveredHasCamera,

                Math.min(
                        // 2)
                        left.coveredHasCamera + right.coveredNoCamera,

                        // 3)
                        left.coveredNoCamera + right.coveredHasCamera));


        // x下方的点都被covered，x也被cover，且x上有相机
        long coveredHasCamera =
                Math.min(left.uncovered, Math.min(left.coveredNoCamera, left.coveredHasCamera))

                        + Math.min(right.uncovered, Math.min(right.coveredNoCamera, right.coveredHasCamera))

                        + 1;

        return new Info(uncovered, coveredNoCamera, coveredHasCamera);
    }


    public static class Info2 {
        public int cameras;
        public Status status;

        public Info2(int cameras, Status status) {
            this.cameras = cameras;
            this.status = status;
        }

        public static enum Status {
            UN_COVERED, COVERED_NO_CAMERA, COVERED_HAS_CAMERA
        }
    }

    // 其实思路还是一样的, 只是代码表现不一样.
    public static int minCameraCover2(TreeNode root) {
        Info2 ans = process2(root);
        if(ans.status == Info2.Status.UN_COVERED)
            return ans.cameras+1;
        return ans.cameras;
    }

    public static Info2 process2(TreeNode X) {
        if (X == null)   // 被覆盖, 无相机
            return new Info2(0, Info2.Status.COVERED_NO_CAMERA);
        Info2 lInfo = process2(X.left);
        Info2 rInfo = process2(X.right);
        int cameras = lInfo.cameras + rInfo.cameras;    // 基本的左孩子和右孩子的相机数量
        // 如果左边或右边没被覆盖, 这里必须放一个相机
        if (lInfo.status == Info2.Status.UN_COVERED || rInfo.status == Info2.Status.UN_COVERED)
            return new Info2(cameras + 1, Info2.Status.COVERED_HAS_CAMERA);
        // 如果左边或右边放了一个相机, 那么当前不放相机最好
        if (lInfo.status == Info2.Status.COVERED_HAS_CAMERA || rInfo.status == Info2.Status.COVERED_HAS_CAMERA)
            return new Info2(cameras, Info2.Status.COVERED_NO_CAMERA);
        return new Info2(cameras, Info2.Status.UN_COVERED);
    }

}
